package basic.courseLearn15.problem;

import org.junit.Test;

import java.util.Arrays;

// 数组，为一堆可重复面额的硬币，先给定金额，求组成面额的硬币数目的所有方法数
public class CoinMethodNum {

    @Test
    public void test_solution_1(){
        int[] arr = {1,2,3,2};
        int sum = 5;
        int result = solution_1(arr,sum,0,0);
        System.out.println("solution_1 :  "+result);
    }

    @Test
    public void test_solution_2(){
        int[] arr = {1,2,3,2};
        int sum = 5;
        int[][] memo = new int[arr.length][sum+1];
        for (int i = 0; i < memo.length; i++) {
            for (int j = 0; j < memo[0].length; j++) {
                memo[i][j] = -2;
            }
        }
        int result = solution_2(arr,sum,0,0,memo);
        System.out.println("solution_2 :  "+result);
    }

    @Test
    public void test_solution_3(){
        int[] arr = {1,2,3,2};
        int sum = 5;
        int result = solution_3(arr,sum,0,0);
        System.out.println("solution_3 :  "+result);
    }

    @Test
    public void test_checkResult(){
        int count=10000;
        int range=100;
        checkResult(count,range);
    }

    /**
     * 对数器
     * @param count 次数
     * @param range 范围（1-range）
     */
    public void checkResult(int count,int range){
        System.out.println("对数器开始运行");
        for (int i = 0; i < count; i++) {
            System.out.println(""+(i+1)+"次测试开始");
            int length=(int)Math.random()*range+1; //[1,range]
            int sum = (int)Math.random()*length+1; //[1,length]
            int[] arr=new int[length];
            for(int j=0;j<arr.length;j++){
                arr[j]=(int)Math.random()*length+1; //[1,length]
            }
            int[][] memo=new int[length][sum];
            for(int k=0;k<memo.length;k++){
                for(int j=0;j<memo[0].length;j++){
                    memo[k][j]=-2;
                }
            }

            int result_1 = solution_1(arr, sum, 0, 0);
            int result_2 = solution_2(arr, sum, 0, 0,memo);
            int result_3 = solution_3(arr, sum, 0, 0);
            if(result_1!= result_2 ){
                System.out.println("第"+(i+1)+"次测试失败");
                System.out.println("arr: "+ Arrays.toString(arr)+", sum: "+sum+", result_1: "+result_1+", result_2: "+result_2+", result_3: "+result_3);
                return;
            }

        }
        System.out.println("\n对数器运行结束，全部测试通过");

    }

    /**
     * 方法一：暴力递归
     * @param arr 数组，为一堆可重复面额的硬币
     * @param sum 指定金额
     * @param currentIndex 当前索引
     * @param currentSum 当前总和
     * @return
     */
    public int solution_1(int[] arr,int sum,int currentIndex,int currentSum){
        //1. 超过边界
        if (currentIndex >= arr.length ){
            if (currentSum == sum){
                return 1;
            }else{
                return 0;
            }
        }
        //2. 超过金额
        if (currentSum > sum){
            return 0;
        }
        //3. 判断是否选中当前硬币
        //3.1 选中当前硬币
        int choose = solution_1(arr,sum,currentIndex+1,currentSum+arr[currentIndex]);
        //3.2 不选中当前硬币
        int notChoose = solution_1(arr,sum,currentIndex+1,currentSum);
        //3.3 判断
        return choose + notChoose;
    }

    /**
     * 方法二：记忆表搜索
     * @param arr 数组，为一堆可重复面额的硬币
     * @param sum 指定金额
     * @param currentIndex 当前索引
     * @param currentSum 当前总和
     * @param memo 记忆表，用于存储中间结果，避免重复计算，-2表示未计算，-1表示计算过，其他值表示计算结果
     * @return
     */
    public int solution_2(int[] arr,int sum,int currentIndex,int currentSum,int[][] memo){
        //1. 超过边界
        if (currentIndex >= arr.length ){
            if (currentSum == sum){
                return 1;
            }else{
                return 0;
            }
        }
        //2. 判断是否已经计算过
        if (memo[currentIndex][currentSum] != -2){
            return memo[currentIndex][currentSum];
        }
        //2. 超过金额
        if (currentSum > sum){
            memo[currentIndex][currentSum] = 0;
            return 0;
        }
        //3. 判断是否选中当前硬币
        //3.1 选中当前硬币
        int choose = solution_1(arr,sum,currentIndex+1,currentSum+arr[currentIndex]);
        //3.2 不选中当前硬币
        int notChoose = solution_1(arr,sum,currentIndex+1,currentSum);
        //3.3 判断
        memo[currentIndex][currentSum] = choose + notChoose;
        return choose + notChoose;
    }

    /**
     * 方法三：严格表搜索
     * @param arr 数组，为一堆可重复面额的硬币
     * @param sum 指定金额
     * @param currentIndex 当前索引
     * @param currentSum 当前总和
     * @return
     */
    public int solution_3(int[] arr,int sum,int currentIndex,int currentSum){
       //1. 定义返回表
        int[][] result = new int[arr.length+1][sum+1];
        //2. 初始化
        for (int j = 0; j < sum+1; j++) {
            if (j == sum){
                result[arr.length][j] = 1;
            }else{
                result[arr.length][j] = 0;
            }
        }
        //3. 填表
        for (int i = arr.length-1; i >= 0; i--) {
            for (int j = 0; j < sum+1; j++) {
                int notChoose = result[i+1][j];
                int choose = 0;
                if( j+arr[i] <= sum){
                    choose = result[i+1][j+arr[i]];
                }
                result[i][j] = notChoose + choose;
            }
        }
        return result[0][0];
    }




}
